﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _10_IsMatch
{
    class Program
    {
        static void Main(string[] args)
        {
            string str1 = "aa";
            string str2 = "a*";

            Console.Write(IsMatch(str1, str2));

            Console.ReadLine();
        }

        private static bool IsMatch(string s, string p)
        {
            if (s == null || p == null)
            {
                return false;
            }
            bool[,] dp = new bool[s.Length + 1,p.Length + 1];
            dp[0,0] = true;
            for (int i = 0; i < p.Length; i++)
            {
                if (p[i] == '*' && dp[0,i - 1])
                {
                    dp[0,i + 1] = true;
                }
            }
            for (int i = 0; i < s.Length; i++)
            {
                for (int j = 0; j < p.Length; j++)
                {
                    if (p[j] == '.')
                    {
                        dp[i + 1,j + 1] = dp[i,j];
                    }
                    if (p[j] == s[i])
                    {
                        dp[i + 1,j + 1] = dp[i,j];
                    }
                    if (p[j] == '*')
                    {
                        if (p[j - 1] != s[i] && p[j - 1] != '.')
                        {
                            dp[i + 1,j + 1] = dp[i + 1,j - 1];
                        }
                        else
                        {
                            dp[i + 1,j + 1] = (dp[i + 1,j] || dp[i,j + 1] || dp[i + 1,j - 1]);
                        }
                    }
                }
            }
            return dp[s.Length,p.Length];
        }
    }
}
